package BinaryTree;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

public class BM39序列化二叉树 {
    //本体思想，层序遍历将二叉树转换成数组
    //对i(i从0开始)位置的节点来说，左孩子是2*i+1,有孩子是2*i+2
    int INF = 0x3f3f3f3f;
    TreeNode emptyNode = new TreeNode(INF);

    String Serialize(TreeNode root) {
        //层序遍历
        if(root==null){
            return null;
        }
        // 使用队列进行层序遍历，起始先将 root 放入队列
        Deque<TreeNode> queue = new LinkedList<>();
        StringBuilder sb = new StringBuilder();  //记录过程
        queue.addLast(root);
        while(!queue.isEmpty()){
            // 每次从队列中取出元素进行「拼接」，包括「正常节点」和「叶子节点对应的首位空节点」
            TreeNode node = queue.pollFirst();
            sb.append(node.val+",");
            // 如果取出的节点不为「占位节点」，则继续往下拓展，同时防止「占位节点」不继续往下拓展
            if(!node.equals(emptyNode)){
                queue.addLast(node.left!=null ? node.left : emptyNode);
                queue.addLast(node.right!=null ? node.right : emptyNode);
            }
        }
        return sb.toString();
    }

    TreeNode Deserialize(String str) {
        if(str==null || "".equals(str)){
            return null;
        }
        // 根据分隔符进行分割
        String[] ss = str.split(",");
        //根据满二叉树规律反序列化
        //使用队列进行层序遍历，起始先将 root 构建出来，并放入队列
        TreeNode root = new TreeNode(Integer.parseInt(ss[0]));
        Deque<TreeNode> q = new ArrayDeque<>();
        q.addLast(root);
        for(int i=1;i<ss.length-1;i+=2){
            TreeNode node = q.pollFirst();
            int a = Integer.parseInt(ss[i]); //左叶子值
            int b = Integer.parseInt(ss[i + 1]);//右叶子值
            if(a!=INF){
                node.left = new TreeNode(a);
                q.addLast(node.left);
            }
            if(b!=INF){
                node.right = new TreeNode(b);
                q.addLast(node.right);
            }
        }
        return root;
    }
}
